package com.dragon.array;

import java.util.Arrays;

/**
 * @author dragon
 * @version 1.0
 * @description 动态数组
 * @date created in 2018-12-10
 */
public class DynamicArray<E> {

    private E[] obj;

    private int size;

    private static Object[] EMPTY_ARRAY = {};

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空参构造
     */
    public DynamicArray() {
        obj = (E[]) EMPTY_ARRAY;
        size = 0;
    }

    /**
     * 有参构造,初始化capacity容量进行数组的初始化
     *
     * @param capacity
     */
    public DynamicArray(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity:" + capacity);
        } else if (capacity == 0) {
            obj = (E[]) EMPTY_ARRAY;
        } else {
            obj = (E[]) new Object[capacity];
        }
        size = 0;
    }

    /**
     * 得到数组中元素的个数
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 判断数组元素是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素
     *
     * @param e
     */
    public void add(E e) {
        ensuringInternalCapacity(size + 1);
        obj[size] = e;
        size++;
    }

    /**
     * 确保内部容量
     *
     * @param minCapacity
     */
    private void ensuringInternalCapacity(int minCapacity) {
        if (obj == EMPTY_ARRAY) {
            obj = (E[]) new Object[DEFAULT_CAPACITY];
        }
        if (minCapacity > obj.length) {
            grow(minCapacity);
        }
    }

    /**
     * 容量扩张
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = obj.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        E[] newArray = (E[]) new Object[newCapacity];
        System.arraycopy(obj, 0, newArray, 0, Math.min(size, newArray.length));
        obj = newArray;
    }

    /**
     * 在index处添加e元素
     *
     * @param e
     * @param index
     */
    public void add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index out of bounds:" + index);
        }
        ensuringInternalCapacity(size + 1);
        System.arraycopy(obj, index, obj, index + 1, size - index);
        obj[index] = e;
        size++;
    }

    /**
     * 添加元素在数组的开始
     *
     * @param e
     */
    public void addFirst(E e) {
        add(e, 0);
    }

    /**
     * 添加元素在数组的结尾
     *
     * @param e
     */
    public void addLast(E e) {
        add(e, size);
    }

    /**
     * 删除元素
     *
     * @param e
     * @return
     */
    public boolean remove(Object e) {
        if (e == null) {
            for (int i = 0; i < obj.length; i++) {
                if (obj[i] == null) {
                    fastRemove(i);
                    return true;
                }
            }
        } else {
            for (int i = 0; i < obj.length; i++) {
                if (obj[i].equals(e)) {
                    fastRemove(i);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 快速删除
     *
     * @param index
     */
    private void fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(obj, index + 1, obj, index, numMoved);
        }
        obj[--size] = null;
    }

    /**
     * 删除元素
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        E oldValue = get(index);
        fastRemove(index);
        return oldValue;
    }

    /**
     * 通过索引获取到元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("get failed,out of bounds:" + index);
        }
        return obj[index];
    }

    /**
     * 在 index角标处设置e元素
     *
     * @param e
     * @param index
     */
    public void set(E e, int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("set failed,out of bounds" + index);
        }
        obj[index] = e;
    }

    /**
     * 判断动态数组是否包含某个元素
     *
     * @param o
     * @return
     */
    public boolean contains(Object o) {
        return indexof(o) != -1;
    }

    /**
     * 返回指定元素在动态数组中第一次出现的索引
     *
     * @param o
     * @return
     */
    public int indexof(Object o) {
        if (o == null) {
            for (int i = 0; i < obj.length; i++) {
                if (obj[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < obj.length; i++) {
                if (o.equals(obj[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 返回指定元素在动态数组中第一次出现的索引
     *
     * @param o
     * @return
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size - 1; i >= 0; i--) {
                if (obj[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (o.equals(obj[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 重写Object的toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < obj.length; i++) {
            sb.append(i != obj.length - 1 ? obj[i] + "," : obj[i] + "]\n");
        }
        sb.append("元素个数:" + size + "\n");
        sb.append("容量:" + obj.length);
        return sb.toString();
    }

    /**
     * 动态数组的缩容
     */
    public void trimToSize() {
        if (size < obj.length) {
            obj = (size == 0) ? (E[]) EMPTY_ARRAY : Arrays.copyOf(obj, size);
        }
    }

    /**
     * 清除动态数组中的元素
     */
    public void clear() {
        for (int i = 0; i < obj.length; i++) {
            obj[i] = null;
        }
        size = 0;
    }

    /**
     * 得到容量
     *
     * @return
     */
    public int getCapacity() {
        return obj.length;
    }
}
